#include "KamaCoder.h"
using namespace std;

int KamaCoder126::run2() {
  // 输入
  int n, a1, a2;
  cin >> n;
  while (n--) {
    cin >> a1 >> a2 >> end_x >> end_y;
    memset(moves, 0, sizeof(moves));
    Knight start;
    start.x = a1;
    start.y = a2;
    start.g = 0;
    start.h = Heuristic(start);
    start.f = start.g + start.h;
    astar(start);
    // 清空队列
    while (!que.empty()) que.pop();
    cout << moves[end_x][end_y] << endl;
  }
  return 0;
}

void KamaCoder126::astar(const Knight& k) {
  Knight cur, next;
  que.push(k);
  while (!que.empty()) {
    cur = que.top();
    que.pop();
    if (cur.x == end_x && cur.y == end_y) break;
    // 遍历所有的行走方式
    for (int i = 0; i < 8; i++) {
      next.x = cur.x + dir[i][0];
      next.y = cur.y + dir[i][1];
      // 越界检测
      if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) continue;
      // 查看下一步有没有走过
      if (!moves[next.x][next.y]) {
        // 步数增加
        moves[next.x][next.y] = moves[cur.x][cur.y] + 1;

        // 计算权值
        next.g = cur.g + 5;
        next.h = Heuristic(next);
        next.f = next.g + next.h;
        que.push(next);
      }
    }
  }
}